/**
 * @param {number} n
 * @return {number[]}
 */
 var countBits = function(n) {  // 动态规划  最高有效位heigbit 2的n次方 res[i]=res[i-heigbit]+1;
    let res=[];
    let heigbit=1;
    res[0]=0;
    for(let i=1;i<=n;i++){
        if((i&(i-1))==0){
            heigbit=i;
        }
        res[i]=res[i-heigbit]+1;
    }
    return res;  
}
// var countBits = function(n) {
//     let ans=[];
//     for(let i=0;i<=n;i++){
//         let num=i;
//         let count=0;
//         while(num>0){
//             num&=(num-1);
//             count++;
//             // count +=num&1;
//             // num>>>=1;
//         }
//         ans.push(count);
//     }
//     return ans;
// };